Thuật toán phân cụm là gì? Các bài báo nghiên cứu khoa học

Khái niệm thuật toán phân cụm

Thuật toán phân cụm (clustering algorithm) là nhóm thuật toán trong học máy không giám sát nhằm phân chia tập dữ liệu thành nhiều nhóm sao cho các điểm dữ liệu trong cùng một cụm có đặc điểm tương đồng cao, còn điểm thuộc các cụm khác nhau thì có đặc điểm khác biệt rõ rệt. Đây là công cụ quan trọng trong khai phá dữ liệu khi chưa có nhãn phân loại, cho phép mô hình phát hiện cấu trúc ẩn trong dữ liệu.

Phân cụm không yêu cầu đầu vào là các nhãn đã được định nghĩa, mà thay vào đó, nó dựa trên các tiêu chí đo độ tương đồng như khoảng cách, mật độ hoặc phân phối xác suất để nhóm dữ liệu. Kết quả phân cụm có thể được sử dụng như bước tiền xử lý hoặc khai thác thông tin trong các tác vụ như phân đoạn ảnh, phân tích văn bản, gợi ý sản phẩm, sinh học phân tử và nhiều lĩnh vực liên ngành khác.

Một số đặc điểm nổi bật của phân cụm:

• Không giám sát, không yêu cầu nhãn dữ liệu
• Cho phép phát hiện nhóm dữ liệu tiềm ẩn trong không gian đa chiều
• Kết quả có thể được đánh giá bằng chỉ số nội tại hoặc so với phân cụm lý tưởng (nếu có)

Mục tiêu và nguyên lý hoạt động

Mục tiêu của phân cụm là tối đa hóa sự tương đồng trong nội bộ cụm (intra-cluster similarity) và đồng thời tối thiểu hóa sự tương đồng giữa các cụm (inter-cluster dissimilarity). Điều này thường được thể hiện bằng các hàm mục tiêu hoặc hàm lỗi mà thuật toán cố gắng tối ưu trong quá trình học.

Đối với các thuật toán dựa trên khoảng cách như K-means, một chỉ số phổ biến là tổng sai số bình phương (SSE - Sum of Squared Errors), được định nghĩa như sau:

$SSE = \sum_{i=1}^{k} \sum_{x \in C_i} \|x - \mu_i\|^2$

Trong đó: $k$ là số cụm, $C_i$ là tập hợp điểm trong cụm thứ $i$, $x$ là điểm dữ liệu, và $\mu_i$ là trung tâm cụm thứ $i$. Thuật toán sẽ lặp đi lặp lại quá trình gán điểm và cập nhật trung tâm cho đến khi SSE đạt giá trị cực tiểu hoặc hội tụ.

Tùy vào từng thuật toán, nguyên lý hoạt động có thể thay đổi, ví dụ thuật toán dựa trên mật độ như DBSCAN hoạt động dựa trên định nghĩa điểm lõi (core point) và vùng lân cận mật độ đủ, còn thuật toán phân cấp dựa trên cấu trúc cây phân cấp dữ liệu. Sự lựa chọn nguyên lý phù hợp phụ thuộc vào đặc điểm dữ liệu và mục tiêu phân tích.

Phân loại thuật toán phân cụm

Các thuật toán phân cụm được chia thành nhiều nhóm dựa trên cách tiếp cận và cấu trúc cụm mà chúng tìm kiếm. Dưới đây là các loại phổ biến nhất trong thực tế và nghiên cứu:

• Phân cụm phân vùng (Partitioning): chia dữ liệu thành $k$ cụm rời nhau. Ví dụ: K-means, K-medoids.
• Phân cụm phân cấp (Hierarchical): tạo cây phân cấp mô tả mối quan hệ giữa các điểm. Ví dụ: Agglomerative, Divisive.
• Phân cụm mật độ (Density-based): xác định cụm dựa vào vùng có mật độ điểm cao. Ví dụ: DBSCAN, OPTICS.
• Phân cụm dựa trên lưới (Grid-based): chia không gian dữ liệu thành lưới. Ví dụ: STING, CLIQUE.
• Phân cụm mô hình (Model-based): giả định dữ liệu tuân theo phân phối xác suất. Ví dụ: Gaussian Mixture Models (GMM).

Mỗi loại thuật toán có ưu điểm và nhược điểm riêng. Ví dụ, phân cụm phân vùng nhanh nhưng không phù hợp với cụm có hình dạng phi tuyến, trong khi phân cụm mật độ phát hiện tốt cụm có hình dạng bất kỳ nhưng khó lựa chọn tham số.

Bảng dưới đây tóm tắt so sánh một số đặc trưng của các nhóm thuật toán:

Loại thuật toán	Ví dụ	Yêu cầu biết số cụm	Phát hiện cụm phi tuyến	Xử lý nhiễu
Phân vùng	K-means, K-medoids	Có	Không	Kém
Phân cấp	Agglomerative	Không	Trung bình	Kém
Mật độ	DBSCAN	Không	Tốt	Tốt
Mô hình	GMM	Có	Tốt	Trung bình

K-means và các biến thể

K-means là một trong những thuật toán phân cụm cổ điển và được sử dụng rộng rãi nhất. Nó hoạt động bằng cách chia dữ liệu thành $k$ cụm bằng cách tối thiểu hóa hàm mất mát SSE như đã mô tả ở trên. Thuật toán khởi tạo $k$ trung tâm ngẫu nhiên, sau đó lặp lại hai bước: gán mỗi điểm dữ liệu vào cụm có trung tâm gần nhất và cập nhật trung tâm cụm bằng trung bình các điểm thuộc cụm đó.

Một hạn chế lớn của K-means là nhạy cảm với giá trị khởi tạo. Các trung tâm ban đầu không hợp lý có thể dẫn đến hội tụ về nghiệm cục bộ. Để khắc phục, thuật toán K-means++ được đề xuất, trong đó việc chọn trung tâm ban đầu được thực hiện có chủ đích dựa trên xác suất phân bố theo khoảng cách, giúp cải thiện đáng kể độ ổn định của kết quả (Arthur & Vassilvitskii, 2007).

K-means phù hợp với dữ liệu tuyến tính, cụm hình cầu và không chồng lấn. Tuy nhiên, trong thực tế, các cụm có thể có hình dạng phức tạp, mật độ không đồng đều hoặc chứa nhiễu. Trong những trường hợp đó, các thuật toán khác như DBSCAN hoặc GMM thường được ưu tiên sử dụng.

Thuật toán DBSCAN và phân cụm dựa trên mật độ

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) là một thuật toán phân cụm không yêu cầu biết trước số lượng cụm, được thiết kế để phát hiện các vùng dữ liệu có mật độ cao và tách biệt điểm nhiễu. DBSCAN hoạt động dựa trên khái niệm “vùng lân cận mật độ đủ lớn” thay vì khoảng cách giữa các cụm trung tâm như trong K-means.

Thuật toán sử dụng hai tham số chính: $\varepsilon$ (epsilon) là bán kính tìm kiếm vùng lân cận, và MinPts là số điểm tối thiểu trong vùng này để được xem là một vùng mật độ cao. Một điểm dữ liệu được gọi là "core point" nếu trong bán kính $\varepsilon$ có ít nhất MinPts điểm. Các điểm lân cận của core point cũng sẽ trở thành một phần của cụm nếu chúng nằm trong vùng ảnh hưởng đó.

DBSCAN phân biệt rõ ba loại điểm:

• Core point: điểm có đủ mật độ trong $\varepsilon$-neighborhood
• Border point: nằm trong $\varepsilon$-neighborhood của core point nhưng không phải core point
• Noise point: không thuộc bất kỳ cụm nào

DBSCAN hiệu quả với cụm có hình dạng phi tuyến, kích thước không đồng đều và có khả năng loại bỏ nhiễu. Tuy nhiên, việc chọn đúng giá trị $\varepsilon$ và MinPts không luôn dễ dàng và có thể ảnh hưởng lớn đến kết quả phân cụm. Một cách chọn $\varepsilon$ phổ biến là dùng biểu đồ khoảng cách k-láng giềng (k-distance graph) để xác định điểm “gãy khúc” rõ ràng.

Phân cụm phân cấp (Hierarchical Clustering)

Phân cụm phân cấp xây dựng một cấu trúc dạng cây (dendrogram) biểu diễn mối quan hệ lồng nhau giữa các điểm dữ liệu. Thuật toán không cần biết trước số lượng cụm và rất trực quan để khám phá cấu trúc phân tầng trong dữ liệu.

Có hai chiến lược chính:

• Agglomerative (gộp dần): khởi đầu từ mỗi điểm là một cụm riêng biệt, sau đó lần lượt gộp hai cụm gần nhất cho đến khi chỉ còn một cụm duy nhất.
• Divisive (chia dần): bắt đầu từ một cụm duy nhất chứa toàn bộ dữ liệu, sau đó tách dần thành các cụm nhỏ hơn.

Khoảng cách giữa các cụm được xác định bằng nhiều phương pháp:

• Liên kết đơn (single linkage): khoảng cách giữa hai điểm gần nhất của hai cụm
• Liên kết đầy đủ (complete linkage): khoảng cách giữa hai điểm xa nhất
• Liên kết trung bình (average linkage): trung bình khoảng cách giữa tất cả các cặp điểm

Phân cụm phân cấp có độ linh hoạt cao và cung cấp cái nhìn trực quan tốt, nhưng có chi phí tính toán lớn – thường là $O(n^3)$, không phù hợp với dữ liệu lớn nếu không áp dụng chiến lược tối ưu hóa.

Đánh giá chất lượng phân cụm

Do phân cụm là một bài toán không giám sát, việc đánh giá chất lượng cụm là một vấn đề quan trọng và không dễ dàng. Có hai loại chỉ số đánh giá chính: chỉ số nội tại (dựa vào đặc điểm cụm) và chỉ số ngoại tại (so sánh với nhãn có sẵn nếu có).

Một số chỉ số đánh giá nội tại phổ biến:

• Silhouette Coefficient: đánh giá mức độ phù hợp của mỗi điểm với cụm được gán so với cụm gần nhất kế tiếp.
• Dunn Index: tỉ lệ giữa khoảng cách nhỏ nhất giữa các cụm với đường kính lớn nhất của cụm bất kỳ.
• Calinski-Harabasz Index: tỉ lệ giữa phương sai giữa cụm và trong cụm.

Ví dụ công thức tính hệ số Silhouette:

$s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}$

Trong đó, $a(i)$ là khoảng cách trung bình giữa điểm $i$ và các điểm trong cùng cụm, còn $b(i)$ là khoảng cách trung bình đến cụm gần nhất khác. Giá trị $s(i)$ nằm trong [-1, 1], giá trị càng gần 1 cho thấy phân cụm càng hiệu quả.

Ngoài ra, nếu có nhãn dữ liệu thực (ground truth), ta có thể sử dụng các chỉ số ngoại tại như Adjusted Rand Index (ARI), Normalized Mutual Information (NMI) hoặc Fowlkes-Mallows Index để đánh giá độ tương đồng giữa nhãn và kết quả phân cụm.

Ứng dụng thực tiễn của phân cụm

Phân cụm được áp dụng trong nhiều lĩnh vực khác nhau nhờ khả năng phát hiện nhóm tự nhiên trong dữ liệu. Trong thị trường, doanh nghiệp sử dụng phân cụm để phân khúc khách hàng dựa trên hành vi mua hàng, độ tuổi, vị trí địa lý. Trong sinh học, thuật toán giúp phân nhóm gen có chức năng tương đồng hoặc xác định loại tế bào dựa trên biểu hiện gen.

Trong thị giác máy tính, phân cụm được ứng dụng trong phân đoạn ảnh, nhận dạng đối tượng và trích xuất đặc trưng. Trong xử lý ngôn ngữ tự nhiên, nó hỗ trợ phân nhóm văn bản, phát hiện chủ đề và xây dựng hệ thống gợi ý nội dung.

Ứng dụng phổ biến:

• Phân tích thị trường: phân đoạn khách hàng, định vị thương hiệu
• Sinh học phân tử: phân tích RNA, phân nhóm gen
• An ninh mạng: phát hiện bất thường, phân tích hành vi
• Y tế: phân tích hồ sơ bệnh án, nhóm triệu chứng

Nhiều thư viện mã nguồn mở như Scikit-learn (Python) và cluster (R) hỗ trợ đầy đủ các thuật toán phân cụm, giúp việc triển khai trở nên dễ dàng hơn trong thực tiễn.

Hạn chế và thách thức

Mặc dù hữu ích, các thuật toán phân cụm vẫn tồn tại nhiều hạn chế. Hầu hết các phương pháp nhạy cảm với tham số đầu vào, ví dụ như số cụm $k$ trong K-means hoặc $\varepsilon$ trong DBSCAN. Việc chọn sai giá trị có thể dẫn đến kết quả phân cụm sai lệch.

Phân cụm cũng khó áp dụng hiệu quả với dữ liệu có chiều cao (high-dimensional data) do hiện tượng "lời nguyền chiều không gian" làm giảm đáng kể hiệu quả của các tiêu chí đo khoảng cách. Ngoài ra, khó đánh giá chất lượng phân cụm trong điều kiện không có ground truth.

Các hướng nghiên cứu mới tập trung vào:

• Phát triển thuật toán phân cụm thích nghi với dữ liệu phức tạp
• Kết hợp phân cụm với học sâu (deep clustering)
• Phân cụm bán giám sát hoặc tích hợp dữ liệu từ nhiều nguồn
• Phân cụm thời gian thực cho dữ liệu streaming

Tài liệu tham khảo

1. Jain, A.K. (2010). "Data clustering: 50 years beyond K-means." Pattern Recognition Letters. https://doi.org/10.1016/j.patrec.2009.09.011
2. Arthur, D., & Vassilvitskii, S. (2007). "K-means++: The advantages of careful seeding." Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. https://proceedings.mlr.press/v2/arthur07a/arthur07a.pdf
3. Schubert, E. et al. (2017). "DBSCAN revisited, revisited." ACM Transactions on Database Systems. https://doi.org/10.1145/3068335
4. Pedregosa, F. et al. (2011). "Scikit-learn: Machine Learning in Python." Journal of Machine Learning Research. https://jmlr.csail.mit.edu/papers/v12/pedregosa11a.html
5. Kaufman, L., & Rousseeuw, P.J. (2009). Finding Groups in Data: An Introduction to Cluster Analysis. Wiley.